/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.fjala.softure.tree.sorted;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * Tree Sorter that receives a unordered binary tree and sort it. 
 * 
 * @author Dann Meneses
 */
public class TreeSorter<T extends Comparable<T>> {

    /**
     * Sort a binary tree.
     * 
     * @param tree tree to sort
     * 
     * @return Binary sorted tree
     */
    public SortedBinaryTree<T> sort(SortedBinaryTree<T> tree) {
        List<T> list = asList(tree);
        Collections.sort(list);
        int middle = list.size() / 2;
        BinaryNode<T> root = new BinaryNode<T>(list.get(middle), null);
        buildNode(list, 0, middle - 1, root);
        buildNode(list, middle + 1, list.size() - 1, root);
        return new SortedBinaryTree<T>(root);
    }

    /**
     * Build a list of elements of a tree with its iterator.
     * 
     * @param tree Tree to get the elements.
     * @return A list with all the elements in the tree.
     */
    private List<T> asList(SortedBinaryTree<T> tree) {
        List<T> res = new ArrayList<T>();
        Iterator<T> iterator = tree.iterator();
        while (iterator.hasNext()) {
            T next = iterator.next();
            res.add(next);
        }

        return res;
    }

    /**
     * Build a branch of a tree startin for a root node.
     * 
     * @param list ordered list that contains the node to add to the root node.
     * @param init initial range of the list
     * @param end end range of the list
     * @param root root node
     */
    private void buildNode(List<T> list, int init, int end, BinaryNode<T> root) {
        if (end >= init) {
            BinaryNode<T> node = new BinaryNode<T>(list.get(end), root);
            if (root.getData().compareTo(node.getData()) >= 0) {
                if (root.getParent() == null || root.hasChildren()) {
                    root.left = node;
                    buildNode(list, init, end - 1, node);
                } else {
                    BinaryNode<T> rootParent = (BinaryNode<T>) root.getParent();
                    if (rootParent.getData().compareTo(node.getData()) >= 0) {
                        rootParent.left = node;
                    } else {
                        rootParent.right = node;
                    }
                    node.setParent(rootParent);
                    node.right = root;
                    root.setParent(node);
                    buildNode(list, init, end - 1, node);
                }
            } else {
                root.right = node;
                buildNode(list, init, end - 1, node);
            }
        }
    }
}
